#pragma once
#include <stdexcept>

namespace DS {
	template <class T>
	class queue {
	private:
		typedef struct Node {
			T data;
			struct Node* next;
		} QNode;
		QNode* front_node; // front_node->next points to front
		QNode* rear_node;  // points to rear
		int queueSize;
	public:
		queue();
		bool empty() const;
		int size() const;
		T front() const;
		T back() const;
		void push(T const&);
		void pop();
		T at(int) const;
	};

	template <class T>
	queue<T>::queue() {
		queueSize = 0;
		front_node = new QNode;
		front_node->next = nullptr;
		rear_node = front_node;
	}

	template <class T>
	bool queue<T>::empty() const {
		return front_node->next == nullptr;
	}

	template <class T>
	int queue<T>::size() const {
		return queueSize;
	}

	template <class T>
	T queue<T>::front() const {
		if (empty()) {
			throw std::out_of_range("Queue<>::front(): empty queue");
		}
		return front_node->next->data;
	}

	template <class T>
	T queue<T>::back() const {
		if (empty()) {
			throw std::out_of_range("Queue<>::back(): empty queue");
		}
		return rear_node->data;
	}

	template <class T>
	void queue<T>::push(T const& elem) {
		QNode* temp_ptr = new QNode;
		if (!temp_ptr) {
			throw std::out_of_range("Queue<>::push(): queue overflow");
		}
		temp_ptr->data = elem;
		rear_node->next = temp_ptr;
		temp_ptr->next = nullptr;
		rear_node = temp_ptr;
		queueSize++;
	}

	template <class T>
	void queue<T>::pop() {
		if (empty()) {
			throw std::out_of_range("Queue<>::pop(): queue underflow");
		}
		QNode* temp_ptr = front_node->next;
		front_node->next = temp_ptr->next;
		delete(temp_ptr);
		queueSize--;
	}

	template <class T>
	T queue<T>::at(int n) const {
		QNode* temp_ptr = front_node->next;
		for (int i = 0; i < n; i++) {
			temp_ptr = temp_ptr->next;
		}
		return temp_ptr->data;
	}
}